package Graph;

import java.util.*;

public class Graph<E> implements DirectedGraph<E> {
    // ENode是一个内部类，表示邻接表中表对应的链表的顶点
    private static class ENode {
        int adjvex; // 邻接顶点序号
        float weight;// 存储边的权值
        ENode nextadj; // 下一个邻接表结点
        float[] speedFactor;
        boolean[] vehiclePermission;//vehiclePermission是一个boolean型数组，暂定有5个元素
        //0表示公共汽车 1表示自行车 2表示步行

        // 构造方法
        public ENode(int adjvex, float weight) {
            this.adjvex = adjvex;
            this.weight = weight;
        }
    }

    // VNode是一个内部类，表示邻接表中第一列的元素
    private static class VNode<E> {
        E data; // 顶点信息
        ENode firstAdjvex; // //邻接表的第1个结点


        public VNode(E data) {
            this.data = data;
        }
    }
    final private int MAXSIZE = 500;// 顶点的最大数量
    private  VNode<E>[] vexs; // 顶点数组
    private int numOfVexs = 0;// 当前顶点数量
    private final int KINDS_OF_VEHICLE = 3;//

    private float[] vehicleSpeed;
    private final float BUS_SPEED = 600;//600m/min
    private boolean takeCampusBus;
    private boolean onlyWalk;

    public Graph() {
        this.vexs = new VNode[MAXSIZE];
    }

    public boolean setVehicleSpeed() {
        Scanner sc = new Scanner(System.in);
        if(this.vehicleSpeed == null) this.vehicleSpeed = new float[KINDS_OF_VEHICLE];
        else{
            for(int i = 0; i < KINDS_OF_VEHICLE; i++){
                this.vehicleSpeed[i] = sc.nextFloat();
            }
        }
        sc.close();
        return true;
    }


    public boolean resetVehicleSpeed() {
        if(this.vehicleSpeed == null) {
            this.vehicleSpeed = new float[KINDS_OF_VEHICLE];
            vehicleSpeed[0] = 500;//公交车400m/min
            vehicleSpeed[1] = 300;//自行车300m/min
            vehicleSpeed[2] = 100;//步行100m/min
        }
        else{
            vehicleSpeed[0] = 500;//公交车400m/min
            vehicleSpeed[1] = 300;//自行车300m/min
            vehicleSpeed[2] = 100;//步行100m/min
        }
        return true;
    }

    public int getNumOfVertex() {
        return numOfVexs;
    }

    public boolean insertVex(E v) {
        if(numOfVexs >= MAXSIZE) {
            return false;
        }
        else {

            VNode<E> vex = new VNode<>(v);
            vexs[numOfVexs] = vex;
            numOfVexs++;
            return true;
        }
    }
    //删除顶点操作，有点麻烦，因为要删除的不仅是邻接表第一列的顶点，还有在邻接的表中出现过的该顶点
    //并且该方法最好先实现查找
    public boolean deleteVex(E v) {

        if(numOfVexs == 0) return false;
        int index1 = indexOfVex(v);

        if(index1 == -1) return false;
        else {

            ENode Vex1;
            ENode Vex2;
            //以下的for循环将邻接表的所有邻接边中，指向待删除编号顶点的边删除，指向编号大于待删除顶点的顶点的编号自减1
            //自减1是因为之后会把待删除顶点在邻接表中删除，其编号被后续的顶点替补。
            for(int i = 0; i < numOfVexs; i++)
            {
                if(i != index1 ) {
                    Vex1 = vexs[i].firstAdjvex;
                    if(Vex1 != null) {
                        if(Vex1.adjvex > index1)
                        {
                            Vex1.adjvex--;
                        }
                        else if(Vex1.adjvex == index1)
                        {
                            vexs[i].firstAdjvex = vexs[i].firstAdjvex.nextadj;
                        }

                        Vex2 = Vex1;
                        Vex1 = Vex1.nextadj;
                        //vex2是vex1的前驱，若vex1指向了待删除点，则vex2的后继设置成vex1的后继
                        //若vex1指向了大于待删除点的序号，则把待删除点的序号--
                        while(Vex1 != null)
                        {
                            if(Vex1.adjvex > index1)
                            {
                                Vex1.adjvex--;
                            }
                            else if(Vex1.adjvex == index1)
                            {
                                Vex2.nextadj = Vex1.nextadj;
                            }
                            Vex1 = Vex1.nextadj;
                            Vex2 = Vex2.nextadj;
                        }
                    }
                }
            }
            //删除第index行操作，需要把第index+1行依次往前移动
            if (numOfVexs - index1 >= 0) System.arraycopy(vexs, index1 + 1, vexs, index1, numOfVexs - index1);

            vexs[numOfVexs] = null;
            numOfVexs--;

        }
        return true;

    }

    //返回顶点的编号
    public int indexOfVex(E v) {
        if(numOfVexs == 0) return -1;

        for(int i = 0;i < numOfVexs;i++) {
            if(vexs[i].data.equals(v)) return i;
        }
        return -1;
    }

    public E getValueOfVex(int v) {
        if(v < 0 || v >= numOfVexs)
            return null;
        else
            return vexs[v].data;
    }

    public boolean insertEdge(int start, int end,float weight) {
        if(start < 0 || start >= numOfVexs || end < 0 || end >= numOfVexs || weight <= 0) {
            return false;
        }
        else {
            if(vexs[start].firstAdjvex == null) {
                vexs[start].firstAdjvex = new ENode(end, weight);
                resetFactors(vexs[start].firstAdjvex);
                resetVehiclePermission(vexs[start].firstAdjvex);
            }
            else {
                ENode vex = vexs[start].firstAdjvex;
                while(vex.nextadj != null) {
                    vex = vex.nextadj;
                }
                vex.nextadj = new ENode(end, weight);
                resetFactors(vex.nextadj);
                resetVehiclePermission(vex.nextadj);
            }

            return true;
        }

    }

    public boolean deleteEdge(int start, int end) {
        if(start < 0 || start >= numOfVexs || end < 0 || end >= numOfVexs) {
            return false;
        }
        else {
            ENode vex = vexs[start].firstAdjvex;

            if(vex == null) return false;

            while(vex.nextadj != null && vex.nextadj.adjvex != end ) {
                vex = vex.nextadj;
            }

            if(vex.nextadj == null) return false;

            vex.nextadj = vex.nextadj.nextadj;

            return true;
        }
    }

    public float dijkstra(int v,int des) {
        //求第v个点到各个点的最短距离数组
        if (v < 0 || v >= numOfVexs)
            return -1;

        //若该源点本身是孤立点，直接返回-1，不存在道路
        if(vexs[v].firstAdjvex == null) return -1;

        final int MAX_OF_PATHS = 200;
        //假设最大路径数为100
        final float MAX_OF_LENGTH = 999999999;
        //最大路径长度为999999999(即正无穷)

        boolean[] confirmed = new boolean[numOfVexs];// 默认初始为false
        float[] distance = new float[numOfVexs];// 存放源点到其他点的距离
        int[] path = new int[MAX_OF_PATHS];

        //初始化距离数组
        for (int i = 0; i < numOfVexs; i++) {
            distance[i] = MAX_OF_LENGTH;
        }


        ENode current;
        current = vexs[v].firstAdjvex;

        distance[v] = 0;
        confirmed[v] = true;

        //读入v号顶点的直接邻接边的权值
        while (current != null) {
            distance[current.adjvex] = current.weight;
            path[current.adjvex] = v;
            current = current.nextadj;
        }



        //Dijkstra算法外层循环需要进行n次
        for (int i = 0; i < numOfVexs; i++) {
            float min = MAX_OF_LENGTH;
            int index = -1;

            for (int j = 0; j < numOfVexs; j++) {

                if (!confirmed[j] && distance[j] < min) {
                    index = j;
                    min = distance[j];
                }
            }

            //index点入确定集合
            if (index != -1) {
                confirmed[index] = true;

                //下面开始更新distance数组
                //从index点的邻接点开始遍历，如果邻接点到源点的距离即distance[current.adjvex} > 从index点中继到达
                //该邻接点的距离，则更新distance数组。
                current = vexs[index].firstAdjvex;
                while(current != null) {
                    if(!confirmed[current.adjvex] && (current.weight + min) < distance[current.adjvex] ) {
                        distance[current.adjvex] = current.weight + min;
                        path[current.adjvex] = index;
                    }
                    current = current.nextadj;
                }
            }
        }


        path[v] = -1;
        int[] shortestPath = new int[MAX_OF_PATHS];
        int currentVex = path[des];
        int count = 0;
        shortestPath[0] = des;
        count ++;
        while(currentVex != -1 && count < MAX_OF_PATHS) {
            shortestPath[count++] = currentVex;
            currentVex = path[currentVex];
        }
        if(count == MAX_OF_PATHS) return -1;//没有找到可行的路径时候返回-1

        int temp;
        for(int i = 0; i < count/2;i++) {
            temp = shortestPath[i];
            shortestPath[i] = shortestPath[count -1 - i];
            shortestPath[count - i - 1] = temp;
        }
        for(int i = 0;i < count - 1;i++) {
            System.out.print(getValueOfVex(shortestPath[i])+"->");
        }
        System.out.println(getValueOfVex(shortestPath[count - 1]));

        return distance[des];
    }

    //将拥挤因子全部初始化为1.0
    public boolean resetFactors(ENode Edge) {

        if(Edge == null) return false;
        //将一天分为24个拥挤段，factor[0]表示0-1时间的拥挤因子
        final int hoursOfDay = 24;
        if(Edge.speedFactor == null) Edge.speedFactor = new float[hoursOfDay];
        //默认赋值1.0
        for(int i = 0; i < 24; i++) {
            Edge.speedFactor[i] = 1;
        }

        return true;
    }

    //输入拥挤因子
    public boolean setFactors(ENode Edge) {

        if(Edge == null ) return false;

        Scanner sc = new Scanner(System.in);
        System.out.println("请输入x时的拥挤因子y,先x后y");
        int hour = sc.nextInt();
        if(hour < 0 || hour > 23) return false;
        else Edge.speedFactor[hour] = sc.nextFloat();
        sc.close();
        return true;
    }
    //恢复至默认状态(只允许步行)
    public boolean resetVehiclePermission(ENode Edge){
        if(Edge == null) return false;

        if(Edge.vehiclePermission == null) Edge.vehiclePermission = new boolean[KINDS_OF_VEHICLE];
        for(int i = 0;i < KINDS_OF_VEHICLE - 1;i++) {
            Edge.vehiclePermission[i] = false;
        }
        Edge.vehiclePermission[KINDS_OF_VEHICLE - 1] = true;
        return true;
    }

    public boolean setVehiclePermission(ENode Edge) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请先后输入公交车 自行车的可用性");
        for(int i = 0;i < KINDS_OF_VEHICLE - 1; i++) {
            Edge.vehiclePermission[i] = sc.nextBoolean();
        }
        sc.close();
        return true;
    }

    public ENode edgeOf(int src, int des) {

        ENode current = vexs[src].firstAdjvex;

        while(current != null){
            if(current.adjvex == des) break;
            else current = current.nextadj;
        }
        return current;

    }
    public float shortestTimeWithVehicles(int v,int des, Calendar calendar,boolean ifOnlyWalk) {
        //求第v个点到各个点的最短距离数组
        if (v < 0 || v >= numOfVexs)
            throw new ArrayIndexOutOfBoundsException();
        //如果起点终点相同，直接返回0
        if(v == des) return 0;

        //若该源点本身是孤立点，直接返回-1，不存在道路
        if(vexs[v].firstAdjvex == null) return -1;

        final int MAX_OF_PATHS = 200;
        //假设最大路径数为100
        final float MAX_OF_LENGTH = 999999999;
        //最大路径长度为999999999(即正无穷)

        boolean[] confirmed = new boolean[numOfVexs];// 默认初始为false
        float[] distance = new float[numOfVexs];// 存放源点到其他点的距离
        int[] path = new int[MAX_OF_PATHS];

        //初始化距离数组
        for (int i = 0; i < numOfVexs; i++) {
            distance[i] = MAX_OF_LENGTH;
        }


        ENode current = vexs[v].firstAdjvex;

        distance[v] = 0;
        confirmed[v] = true;
        //优先选择靠前的交通工具
        int VehicleToSelect;
        //0是公交车 1是自行车 2是步行

        //读入v号顶点的直接邻接边的权值
        while (current != null) {
            if(!ifOnlyWalk) {
                for (VehicleToSelect = 0; !current.vehiclePermission[VehicleToSelect]; VehicleToSelect++) {
                }
                distance[current.adjvex] = current.weight / (vehicleSpeed[VehicleToSelect] * current.speedFactor[calendar.get(Calendar.HOUR_OF_DAY)]);
            }
            else{
                distance[current.adjvex] = current.weight / (vehicleSpeed[KINDS_OF_VEHICLE - 1] * current.speedFactor[calendar.get(Calendar.HOUR_OF_DAY)]);
            }
            path[current.adjvex] = v;
            current = current.nextadj;
        }



        //Dijkstra算法外层循环需要进行n次
        for (int i = 0; i < numOfVexs; i++) {
            float min = MAX_OF_LENGTH;
            int index = -1;

            for (int j = 0; j < numOfVexs; j++) {

                if (!confirmed[j] && distance[j] < min) {
                    index = j;
                    min = distance[j];
                }
            }

            //index点入确定集合
            if (index != -1) {
                confirmed[index] = true;

                //下面开始更新distance数组
                //从index点的邻接点开始遍历，如果邻接点到源点的距离即distance[current.adjvex} > 从index点中继到达
                //该邻接点的距离，则更新distance数组。
                current = vexs[index].firstAdjvex;
                while(current != null) {
                    if(!ifOnlyWalk) {
                        for (VehicleToSelect = 0; !current.vehiclePermission[VehicleToSelect]; VehicleToSelect++) {
                        }
                        if (!confirmed[current.adjvex] && ((current.weight
                                / (vehicleSpeed[VehicleToSelect]
                                * current.speedFactor[calendar.get(Calendar.HOUR_OF_DAY)])
                                + min) < distance[current.adjvex])) {
                            distance[current.adjvex] = current.weight
                                    / (vehicleSpeed[VehicleToSelect]
                                    * current.speedFactor[calendar.get(Calendar.HOUR_OF_DAY)]);
                            path[current.adjvex] = index;
                        }
                    }
                    else{
                        if (!confirmed[current.adjvex] && ((current.weight
                                / (vehicleSpeed[KINDS_OF_VEHICLE - 1]
                                * current.speedFactor[calendar.get(Calendar.HOUR_OF_DAY)])
                                + min) < distance[current.adjvex])) {
                            distance[current.adjvex] = current.weight
                                    / (vehicleSpeed[KINDS_OF_VEHICLE - 1]
                                    * current.speedFactor[calendar.get(Calendar.HOUR_OF_DAY)]);
                            path[current.adjvex] = index;
                        }
                    }
                    current = current.nextadj;
                }
            }
        }


        path[v] = -1;
        int[] shortestPath = new int[MAX_OF_PATHS];
        int currentVex = path[des];
        int count = 0;
        shortestPath[0] = des;
        count ++;
        while(currentVex != -1 && count < MAX_OF_PATHS) {
            shortestPath[count++] = currentVex;
            currentVex = path[currentVex];
        }
        if(count == MAX_OF_PATHS) return -1;//没有找到可行的路径时候返回-1


        for(int i = 0; i < count/2;i++) {
            int temp = shortestPath[i];
            shortestPath[i] = shortestPath[count -1 - i];
            shortestPath[count - i - 1] = temp;
        }
        for(int i = 0;i < count - 1;i++) {
            System.out.print(getValueOfVex(shortestPath[i])+"->");
        }
        System.out.println(getValueOfVex(shortestPath[count - 1]));

        return distance[des];
    }


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("功能1：添加点 功能2：查看点的编号");
        System.out.println("功能3：添加边 功能4：查看点的总数");
        System.out.println("功能5：以编号查询点的数据 功能6：最短路径算法");
        System.out.println("功能7：删除点 功能8：删除边");
        System.out.println("功能9：最短时间算法 功能10：设置拥挤因子");
        System.out.println("功能11：恢复默认拥挤因子1.0 功能12：设置交通工具可用性");
        System.out.println("功能13：恢复默认交通工具可行性");
        int fun = sc.nextInt();
        Graph<Building> G = new Graph<Building>();
        G.resetVehicleSpeed();

        while(fun != 0) {
            switch(fun) {
                case 1:
                    String data1;
                    System.out.println("请输入建筑的名称与校区");
                    Building B1 = new Building(sc.next(),sc.next());
                    G.insertVex(B1);
                    break;
                case 2:
                    System.out.println("请输入建筑名称，建筑所在校区");
                    Building B2 = new Building(sc.next(),sc.next());
                    System.out.println("其编号为"+G.indexOfVex(B2));
                    break;
                case 3:
                    int src,des;
                    float weight;
                    System.out.println("请依次输入起始点名称，起始点校区、终止点、终止点校区、边的权");
                    Building B3 = new Building(sc.next(),sc.next());
                    src = G.indexOfVex(B3);
                    Building B4 = new Building(sc.next(),sc.next());
                    des = G.indexOfVex(B4);
                    weight = sc.nextInt();
                    G.insertEdge(src, des, weight);
                    break;
                case 4:
                    System.out.println("当前顶点总数为"+G.getNumOfVertex());
                    break;
                case 5:
                    int v = sc.nextInt();
                    Building data5 = G.getValueOfVex(v);
                    if(data5 != null) System.out.println("编号为"+ v +"的点的数据为" + data5);
                    else  System.out.println("Error!");
                    break;
                case 6:
                    System.out.println("请依次输入起始点名称,校区，终止点名称,校区");
                    int start = G.indexOfVex(new Building(sc.next(),sc.next()));
                    int end = G.indexOfVex(new Building(sc.next(),sc.next()));
                    float totalWeight = G.dijkstra(start, end);
                    if (totalWeight != -1) System.out.println("总长度为" + totalWeight);
                    else System.out.println("错误，未找到可行路径");
                    break;

                case 7:
                    System.out.println("请输入待删除点的名称与校区");
                    if(G.deleteVex(new Building(sc.next(),sc.next()))) System.out.println("删除成功");
                    else System.out.println("删除失败");
                    break;
                case 8:
                    System.out.println("请依次输入待删除边的起始点名称、校区、终止点名称、校区");
                    int start2 = G.indexOfVex(new Building(sc.next(),sc.next()));
                    int end2 = G.indexOfVex(new Building(sc.next(),sc.next()));
                    if(G.deleteEdge(start2,end2)) System.out.println("删除成功");
                    else System.out.println("删除失败");
                    break;

                case 9:
                    //最短交通工具时间算法
                    System.out.println("请依次输入起始点名称,校区，终止点名称,校区");
                    int start3 = G.indexOfVex(new Building(sc.next(),sc.next()));
                    int end3 = G.indexOfVex(new Building(sc.next(),sc.next()));
                    System.out.println("是否乘坐校园班车？");
                    G.takeCampusBus = sc.nextBoolean();
                    System.out.println("是否选用非步行的交通工具");
                    G.onlyWalk = !sc.nextBoolean();
                    Calendar cld = Calendar.getInstance();
                    if(G.getValueOfVex(start3).campus.equals(G.getValueOfVex(end3).campus)) {
                        float totalTime = G.shortestTimeWithVehicles(start3, end3, cld, G.onlyWalk);
                        if (totalTime != -1) System.out.println("总时间为" + totalTime);
                        else System.out.println("错误，未找到可行路径");
                    }
                    //优先乘坐校园班车的情况
                    else if(G.takeCampusBus){
                        int busStation1 = G.indexOfVex(new Building("校园班车站",G.getValueOfVex(start3).campus));
                        /*
                        if(cld.get(Calendar.HOUR_OF_DAY) >= 21 || cld.get(Calendar.HOUR_OF_DAY) <= 5){
                            System.out.println("此时太早或者太晚，请稍后再试。校园班车的发车时间是7点-21点，每2h一班");
                            break;
                        }
                        */
                        float totalTime = G.shortestTimeWithVehicles(start3, busStation1, cld, G.onlyWalk);

                        if(totalTime != -1){
                            int busStation2 = G.indexOfVex(new Building("校园班车站",G.getValueOfVex(end3).campus));
                            ENode edge = G.edgeOf(busStation1 , busStation2);
                            if(edge == null) {
                                System.out.println("错误，校园班车暂未开通");
                                break;
                            }
                            float waitTime = 60 - cld.get(Calendar.MINUTE) + 60 * (cld.get(Calendar.HOUR_OF_DAY) % 2);

                            totalTime += waitTime;
                            totalTime += edge.weight / (G.BUS_SPEED * edge.speedFactor[cld.get(Calendar.HOUR_OF_DAY)]);
                            float length = G.shortestTimeWithVehicles(busStation2, end3, cld, G.onlyWalk);
                            if(length != -1) {
                                totalTime += length;
                                System.out.printf("等待下一班班车发车的时间为%.2f,总时间为%.2f\n", waitTime,
                                                                                          totalTime);
                            }
                            else System.out.println("错误，未找到可行路径");

                        }
                        else System.out.println("错误，未找到可行路径");
                    }
                    //使用普通交通工具的情况
                    else {
                        float totalTime = G.shortestTimeWithVehicles(start3, end3, cld, G.onlyWalk);
                        if(totalTime == -1) System.out.println("错误，未找到可行路径");
                        else System.out.printf("总时间为%.2f",totalTime);
                    }
                    break;
                case 10:
                    System.out.println("请输入需要设置拥挤因子的起始点与终点（包含校区信息）");
                    ENode edge = G.edgeOf( G.indexOfVex(new Building(sc.next(),sc.next())),
                                           G.indexOfVex(new Building(sc.next(),sc.next())));
                    if(G.setFactors(edge)) System.out.println("设置拥挤因子成功");
                    else System.out.println("设置拥挤因子失败");
                    break;
                case 11:
                    System.out.println("请输入需要恢复默认拥挤因子的起始点与终点（包含校区信息）");
                    ENode edge1 = G.edgeOf( G.indexOfVex(new Building(sc.next(),sc.next())),
                            G.indexOfVex(new Building(sc.next(),sc.next())));
                    if(G.resetFactors(edge1)) System.out.println("恢复拥挤因子成功");
                    else System.out.println("恢复拥挤因子失败");
                    break;
                case 12:
                    System.out.println("请输入需要设置交通工具可用性的起始点与终点(包含校区信息)");
                    ENode edge2 = G.edgeOf( G.indexOfVex(new Building(sc.next(),sc.next())),
                            G.indexOfVex(new Building(sc.next(),sc.next())));
                    if(G.setVehiclePermission(edge2)) System.out.println("设置交通工具可用性成功");
                    else System.out.println("设置交通工具可用性失败");
                    break;
                case 13:
                    System.out.println("请输入需要恢复默认交通工具可用性的起始点与终点(包含校区信息)");
                    ENode edge3 = G.edgeOf( G.indexOfVex(new Building(sc.next(),sc.next())),
                            G.indexOfVex(new Building(sc.next(),sc.next())));
                    if(G.resetVehiclePermission(edge3)) System.out.println("恢复默认交通工具可用性成功");
                    else System.out.println("恢复默认交通工具可用性失败");
                    break;

            }
            fun = sc.nextInt();

        }
    }
}

class Building{
    String name;
    String campus;

    public Building(String name,String campus){
        this.name = name;
        this.campus = campus;
    }

    public Building(String name){
        this.name = name;
        this.campus = "主校区";
    }

    public boolean equals(Object obj) {
        if(obj instanceof Building){
            Building target = (Building) obj;
            return this.name.equals(target.name) && this.campus.equals((target.campus));
        }
        else return false;
    }

    public String toString(){
        return (this.name + "(" + this.campus + ")" );
    }
}
